﻿using System.Globalization;
using System;
using System.Collections.Generic;
using System.Text;
using Ndo.Text;

namespace Ndo.Maths
{
    public class BigInteger : Integer<BigInteger>, IClone<BigInteger>, IConvertible
    {
        [ParsingPattern(@"(\+|-)?\d+")]
        public BigInteger(string text)
        {
            BigInteger i = Parse(text);
            data = i.data;
            isNegative = i.isNegative;
            length = i.length;
        }
        public BigInteger()
            : this(new uint[] { 1 }, false)
        { }
        public BigInteger(byte[] data)
            :this(data, false)
        {}
        public BigInteger(byte[] data, bool isNegative)
            : this(bufferData(data), isNegative)
        {}
        private static uint[] bufferData(byte[] data)
        {
            uint[] ret = new uint[(data.Length+3)/4];
            Buffer.BlockCopy(data, 0, ret, 0, data.Length);
            return ret;
        }
        private BigInteger(uint[] data, bool isNegative)
        {
            this.data = data;
            this.length = data.Length;
            while (this.length > 0 && data[this.length - 1] == 0)
                this.length--;
            this.isNegative = length == 0 ? false:isNegative;
        }
        private BigInteger(uint[] data, int length, bool isNegative)
        {
            this.data = data;
            this.length = length;
            if (data.Length < length)
            {
                System.Diagnostics.Trace.WriteLine(string.Format("length error {0} {1}", length, data.Length));
                length = data.Length;
            }
            this.isNegative = length==0?false:isNegative;
        }

        private readonly uint[] data;
        private readonly int length;
        private readonly bool isNegative;
        #region implicit opeartors
        public static implicit operator BigInteger(long i)
        {
            unchecked
            {
                bool b = i < 0;
                if (b)
                {
                    i = -i;
                }
                ulong u = (ulong)i;
                return new BigInteger(new uint[] { (uint)u, (uint)(u >> 32) }, b);
            }
        }

        public static implicit operator BigInteger(int i)
        {
            unchecked
            {
                bool b = i < 0;
                if (b)
                {
                    i = -i;
                }
                return new BigInteger(new uint[] { (uint)i }, b);
            }
        }
        public static implicit operator BigInteger(short i)
        {
            unchecked
            {
                int ii = i;
                bool b = ii < 0;
                if (b)
                {
                    ii = -ii;
                }
                return new BigInteger(new uint[] { (uint)ii }, b);
            }
        }
        public static implicit operator BigInteger(sbyte i)
        {
            unchecked
            {
                int ii = i;
                bool b = ii < 0;
                if (b)
                {
                    ii = -ii;
                }
                return new BigInteger(new uint[] { (uint)ii }, b);
            }
        }

        public static implicit operator BigInteger(ulong i)
        {
            unchecked
            {
                return new BigInteger(new uint[] { (uint)i, (uint)(i >> 32) }, false);
            }
        }
        public static implicit operator BigInteger(uint i)
        {
            return new BigInteger(new uint[] { i }, false);
        }
        public static implicit operator BigInteger(ushort i)
        {
            return new BigInteger(new uint[] { i }, false);
        }
        public static implicit operator BigInteger(byte i)
        {
            return new BigInteger(new uint[] { i }, false);
        }
        #endregion

        #region explicit opeartors
        public static explicit operator BigInteger(decimal i)
        {
            int[] bits = decimal.GetBits(decimal.Round(i));
            unchecked
            {
                return new BigInteger(new uint[] { (uint)bits[0], (uint)bits[1], (uint)bits[2] }, bits[3] < 0);
            }
        }
        public static explicit operator BigInteger(double i)
        {
            long m;
            int e;
            if (BitwiseUtilities.GetExponentMantissa(i, out e, out m))
            {
                if (e < 0)
                {
                    if (e <= -63)
                        return Zero;
                    return (BigInteger) (m << e);
                }
                unchecked
                {
                    bool b = m < 0;
                    if (b)
                    {
                        m = -m;
                    }
                    ulong u = (ulong)m;
                    int len = e / 32;
                    uint[] data = new uint[len + 3];
                    data[len + 0] = (uint)(u << ((e % 32) - 0 * 32));
                    data[len + 1] = (uint)(u << ((e % 32) - 1 * 32));
                    data[len + 2] = (uint)(u << ((e % 32) - 2 * 32));
                    return new BigInteger(data, b);
                }
            }
            throw new OverflowException();
        }
        public static explicit operator BigInteger(float i)
        {
            int m;
            int e;
            if (BitwiseUtilities.GetExponentMantissa(i, out e, out m))
            {
                unchecked
                {
                    bool b = m < 0;
                    if (b)
                    {
                        m = -m;
                    }
                    uint u = (uint)m;
                    int len = e / 32;
                    uint[] data = new uint[len + 2];
                    data[len + 0] = (uint)(u << ((e % 32) - 0 * 32));
                    data[len + 1] = (uint)(u << ((e % 32) - 1 * 32));
                    return new BigInteger(data, b);
                }
            }
            throw new OverflowException();
        }
        public static explicit operator decimal(BigInteger i)
        {
            unchecked
            {
                switch (i.length)
                {
                    case 0:
                        return decimal.Zero;
                    case 1:
                        return new decimal((int)i.data[0], 0, 0, i.isNegative, 0);
                    case 2:
                        return new decimal((int)i.data[0], (int)i.data[1], 0, i.isNegative, 0);
                    case 3:
                        return new decimal((int)i.data[0], (int)i.data[1], (int)i.data[2], i.isNegative, 0);
                }
            }
            throw new OverflowException();
        }
        public static explicit operator double(BigInteger i)
        {
            if (i.length == 0)
                return 0.0;
            uint u = i.data[i.length - 1];
            int pos = 0;
            while (u != 0)
            {
                pos++;
                u >>= 1;
            }
            long m;
            int e = (i.length - 3) * 32 + pos + 1;
            m = ((long)u) << (64 - pos);
            if (i.length > 2)
                m |= ((long)i.data[i.length - 2]) << (32 - pos);
            if (i.length > 3)
                m |= ((long)i.data[i.length - 3]) << (0 - pos);
            m >>= 1;
            if (i.isNegative)
                m |= 1L << 63;
            else
                m &= ~(1L << 63);
            return BitwiseUtilities.GetDoubleByExponentMantissa(e, m);
        }
        public static explicit operator float(BigInteger i)
        {
            if (i.length == 0)
                return 0.0f;
            uint u = i.data[i.length - 1];
            int pos = 0;
            while (u != 0)
            {
                pos++;
                u >>= 1;
            }
            int m;
            int e = (i.length - 3) * 32 + pos + 1;
            m = ((int)u) << (32 - pos);
            if (i.length > 2)
                m |= ((int)i.data[i.length - 2]) << (0 - pos);
            m >>= 1;
            if (i.isNegative)
                m |= 1 << 31;
            else
                m &= ~(1 << 31);
            return BitwiseUtilities.GetSingleByExponentMantissa(e, m);
        }

        public static explicit operator ulong(BigInteger i)
        {
            if (!i.isNegative)
                switch (i.length)
                {
                    case 0:
                        return 0UL;
                    case 1:
                        return i.data[0];
                    case 2:
                        return ((ulong)i.data[1] << 32) | (ulong)i.data[0];
                }
            throw new OverflowException();
        }
        public static explicit operator uint(BigInteger i)
        {
            if (!i.isNegative)
                switch (i.length)
                {
                    case 0:
                        return 0;
                    case 1:
                        return i.data[0];
                }
            throw new OverflowException();
        }
        public static explicit operator ushort(BigInteger i)
        {
            if (!i.isNegative)
                switch (i.length)
                {
                    case 0:
                        return 0;
                    case 1:
                        return (ushort)i.data[0];
                }
            throw new OverflowException();
        }
        public static explicit operator byte(BigInteger i)
        {
            if (!i.isNegative)
                switch (i.length)
                {
                    case 0:
                        return 0;
                    case 1:
                        return (byte)i.data[0];
                }
            throw new OverflowException();
        }

        public static explicit operator long(BigInteger i)
        {
            switch (i.length)
            {
                case 0:
                    return 0;
                case 1:
                    if (i.isNegative)
                        return -(long)i.data[0];
                    return (long)i.data[0];
                case 2:
                    ulong u = ((ulong)i.data[1] << 32) | (ulong)i.data[0];
                    if (u < (1UL << 63))
                    {
                        if (i.isNegative)
                            return -(long)u;
                        return (long)u;
                    }
                    if (u == (1UL << 63) && i.isNegative)
                        return long.MinValue;
                    break;
            }
            throw new OverflowException();
        }
        public static explicit operator int(BigInteger i)
        {
            switch (i.length)
            {
                case 0:
                    return 0;
                case 1:
                    if (i.data[0] < (1U << 31))
                    {
                        if (i.isNegative)
                            return -(int)i.data[0];
                        return (int)i.data[0];
                    }
                    if (i.data[0] == (1U << 31) && i.isNegative)
                        return int.MinValue;
                    break;
            }
            throw new OverflowException();
        }
        public static explicit operator short(BigInteger i)
        {
            switch (i.length)
            {
                case 0:
                    return 0;
                case 1:
                    if (i.data[0] < (1U << 15))
                    {
                        if (i.isNegative)
                            return (short)-(int)i.data[0];
                        return (short)i.data[0];
                    }
                    if (i.data[0] == (1UL << 15) && i.isNegative)
                        return short.MinValue;
                    break;
            }
            throw new OverflowException();
        }
        public static explicit operator sbyte(BigInteger i)
        {
            switch (i.length)
            {
                case 0:
                    return 0;
                case 1:
                    if (i.data[0] < (1UL << 7))
                    {
                        if (i.isNegative)
                            return (sbyte)-(int)i.data[0];
                        return (sbyte)i.data[0];
                    }
                    if (i.data[0] == (1UL << 7) && i.isNegative)
                        return sbyte.MinValue;
                    break;
            }
            throw new OverflowException();
        }
        #endregion

        #region Static
        static BigInteger()
        {
            one = new BigInteger();
            zero = new BigInteger(new uint[0], false);
            negativeOne = new BigInteger(new uint[] { 1 }, true);

            Powers10 = new BigInteger[31];
            for (int i = 30; i > 0; i--)
                Powers10[i] = Zero;
            Powers10[0] = 10;
        }
        private static readonly BigInteger uintD9 = new BigInteger(new uint[] { 1000000000 }, false);
        private static readonly BigInteger[] Powers10;
        #region Power10
        public static BigInteger Pow10(int x)
        {
            if (x < 0)
                return Zero;
            int i = 0;
            BigInteger r = One;
            while (x != 0)
            {
                if (Powers10[i].length == 0)
                    Powers10[i] = Powers10[i - 1] * Powers10[i - 1];
                if ((x & 1) != 0)
                    r *= Powers10[i];
                x >>= 1;
                i++;
            }
            return r;
        }

        #endregion
        #endregion


        #region 4 opeartors
        private static BigInteger subtract(uint[] d1, int len1, uint[] d2, int len2)
        {
            bool sign;
            uint[] d;
            int i = len1 - len2;
            if (i > 0)
            {
                sign = false;
                i = len2;
                d = new uint[len1];
                goto Sub;
            }
            if (i < 0)
            {
                d = d1;
                d1 = d2;
                d2 = d;
                sign = true;
                i = len1;
                d = new uint[len1 = len2];
                goto Sub;
            }
            i = len1;
        Loop:
            if (--i < 0)
                return Zero;
            if (d1[i] == d2[i])
                goto Loop;
            if (sign = d1[i] < d2[i])
            {
                d = d1;
                d1 = d2;
                d2 = d;
            }
            d = new uint[len1 = ++i];
        Sub:
            ulong u = 1UL;
            int ii = 0;
            while (ii < i)
            {
                u += (ulong)uint.MaxValue + (ulong)d1[ii] - (ulong)d2[ii];
                unchecked { d[ii] = (uint)u; }
                u >>= 32;
                ii++;
            }
            if (u == 0UL)
            {
                while (d1[ii] == 0)
                    d[ii++] = uint.MaxValue;
                d[ii] = d1[ii] - 1;
                ii++;
            }
            if (ii == len1)
            {
                while (d[--ii] == 0) ;
                return new BigInteger(d, ii + 1, sign);
            }
            while (ii < len1)
            {
                d[ii] = d1[ii];
                ii++;
            }
            return new BigInteger(d, len1, sign);
        }
        private static BigInteger add(uint[] d1, int len1, uint[] d2, int len2, bool sign)
        {
            uint[] d;
            ulong u = 0;
            int i;
            if (len1 < len2)
            {
                d = d1;
                i = len1;
                d1 = d2;
                len1 = len2;
                d2 = d;
                len2 = i;
            }
            d = new uint[len1 + 1];
            i = 0;
            while (i < len2)
            {
                u += (ulong)d1[i] + (ulong)d2[i];
                unchecked
                {
                    d[i] = (uint)u;
                }
                u >>= 32;
                i++;
            }
            if (u != 0)
            {
                while (i < len1 && d1[i] == uint.MaxValue)
                    d[i++] = 0;
                if (i >= len1)
                    d[i] = 1;
                else
                    d[i] = d1[i] + 1;
                i++;
            }
            while (i < len1)
            {
                d[i] = d1[i];
                i++;
            }
            return new BigInteger(d, i, sign);
        }
        public static BigInteger operator +(BigInteger i1, BigInteger i2)
        {
            if (!i1.isNegative)
            {
                if (!i2.isNegative)
                    return add(i1.data, i1.length, i2.data, i2.length, false);
                return subtract(i1.data, i1.length, i2.data, i2.length);
            }
            if (i2.isNegative)
                return add(i1.data, i1.length, i2.data, i2.length, true);
            return subtract(i2.data, i2.length, i1.data, i1.length);
        }
        public static BigInteger operator -(BigInteger i1, BigInteger i2)
        {
            if (!i1.isNegative)
            {
                if (!i2.isNegative)
                    return subtract(i1.data, i1.length, i2.data, i2.length);
                return add(i1.data, i1.length, i2.data, i2.length, false);
            }
            if (i2.isNegative)
                return subtract(i2.data, i2.length, i1.data, i1.length);
            return add(i1.data, i1.length, i2.data, i2.length, true);
        }
        public static BigInteger operator +(BigInteger i)
        {
            return i;
        }
        public static BigInteger operator -(BigInteger i)
        {
            return new BigInteger(i.data, i.length, !i.isNegative);
        }
        public static BigInteger operator *(BigInteger i1, BigInteger i2)
        {
            uint[] d1 = i1.data, d2 = i2.data;
            int l1 = i1.length, l2 = i2.length;
            if (l1 == 0 || l2 == 0)
                return Zero;
            uint[] d = new uint[l1 + l2];
            for (int j1 = 0; j1 < l1; j1++)
            {
                ulong J1 = d1[j1];
                ulong u = 0UL;
                int j = j1;
                for (int j2 = 0; j2 < l2; j2++, j++)
                {
                    u += J1 * (ulong)d2[j2] + (ulong)d[j];
                    unchecked
                    {
                        d[j] = (uint)u;
                    }
                    u >>= 32;
                }
                d[j] = (uint)u;
            }
            return new BigInteger(d, i1.isNegative ^ i2.isNegative);
        }
        public static uint div(uint[] d1, uint[] d2, int l2, int index)
        {
            int ii2 = l2 - 1, ii1 = ii2 + index, i, l1 = l2 + index;
            ulong
                u = (((ulong) (d1[ii1 + 1])) << 32) | d1[ii1], uu = d2[ii2], ret = u;
            if (u < uu)
                return 0;
            if (d2[0] == 1 && l2 == 1)
            {
                uint a = d1[index];
                d1[index] = 0;
                return a;
            }
            if(ii2>0)
            {
                if (ret <= uint.MaxValue)
                {
                    ii1--;
                    ii2--;
                    ret = (ret << 32) | d1[ii1];
                    uu = (uu << 32) | d2[ii2];
                }
                if (ii2 > 0 && ret < (1UL << 63))
                {
                    for (i = 0; ret < (1UL << 63); i++)
                    {
                        ret <<= 1;
                    }
                    ret = ret | (d1[ii1 - 1] >> (32 - i));
                    uu = (uu << i) | (d2[ii2 - 1] >> (32 - i));
                }
            }

            ret = ret/uu;
            uint[] d = new uint[l2 + 1];
#if DEBUG
            int c = 0;
#endif
            Array.Copy(d1, index, d, 0, l2 + 1);
        Loop:
            ii2 = l2 - 1;
            ii1 = ii2 + index;
            for (u = d1[ii1 + 1]; ii2 >= 0; ii1--, ii2--)
            {
                u = (u << 32) | d1[ii1];
                uu = d2[ii2] * ret;
                if (u < uu)
                {
                    i = ii1 + 2;

                    while (i<=l2+index && d1[i] == 0)
                    {
                        d1[i] = uint.MaxValue;
                        i++;
                    }
                    if (i > l2 + index)
                    {
                        ret--;
                        Array.Copy(d, 0, d1, index, l2 + 1);
#if DEBUG
                        c++;
                        if (c > 2)
                        {
                            throw new Exception();
                        }
#endif
                        goto Loop;
                    }
                    d1[i]--;
                }
                u -= uu;
                d1[ii1 + 1] = (uint)(u >> 32);
            }
            d1[ii1 + 1] = (uint)u;
            return (uint)ret;
        }
        public static BigInteger Division(ref BigInteger i1, BigInteger i2)
        {
            if (i2.length == 0)
                throw new DivideByZeroException();
            uint[] d1 = i1.data, d2 = i2.data;
            int len1 = i1.length, len2 = i2.length, i = len1 - len2, j;
            if (i < 0)
                return Zero;
            uint[] r = new uint[len1 + 1];
            Array.Copy(d1, 0, r, 0, len1);
            d1 = new uint[i + 1];
            for (j = i; j >= 0; j--)
                d1[j] = div(r, d2, len2, j);
            i2 = new BigInteger(d1, i1.isNegative ^ i2.isNegative);
            i1 = new BigInteger(r, i1.isNegative);
            return i2;
        }

        public static BigInteger operator /(BigInteger i1, BigInteger i2)
        {
            if (i2.length == 0)
                throw new DivideByZeroException();
            uint[] d1 = i1.data, d2 = i2.data;
            int len1 = i1.length, len2 = i2.length, i = len1 - len2, j;
            if (i < 0)
                return Zero;
            uint[] r = new uint[len1 + 1];
            Array.Copy(d1, 0, r, 0, len1);
            d1 = new uint[i + 1];
            for (j = i; j >= 0; j--)
                d1[j] = div(r, d2, len2, j);
            //i2 = new BigInteger(d1, i1.isNegative ^ i2.isNegative);
            //i1 = new BigInteger(r, i1.isNegative);
            return new BigInteger(d1, i1.isNegative ^ i2.isNegative);
        }
        public static BigInteger operator %(BigInteger i1, BigInteger i2)
        {
            if (i2.length == 0)
                throw new DivideByZeroException();
            uint[] d1 = i1.data, d2 = i2.data;
            int len1 = i1.length, len2 = i2.length, i = len1 - len2, j;
            if (i < 0)
                return i1;
            uint[] r = new uint[len1 + 1];
            Array.Copy(d1, 0, r, 0, len1);
            d1 = new uint[i + 1];
            for (j = i; j >= 0; j--)
                d1[j] = div(r, d2, len2, j);
            //i2 = new BigInteger(d1, i1.isNegative ^ i2.isNegative);
            //i1 = new BigInteger(r, i1.isNegative);
            return new BigInteger(r, i1.isNegative);
        }
        #endregion;

        //#region Bits operator
        //public static BigInteger operator &(BigInteger i1, BigInteger i2)
        //{
        //    uint[] data1 = i1.data, data2 = i2.data, data;
        //    if(data1.Length>data2.Length)
        //    {
        //        data1 = (uint[])data1.Clone();
        //    }
        //    else
        //    {
        //        data = data1;
        //        data1 = (uint[])data2.Clone();
        //        data2 = data;
        //    }
        //    for(int i=data2.Length-1; i>=0; i--)
        //    {
        //        data1[i] &= data2[i];
        //    }
        //    return new BigInteger(data1, false);
        //}
        //public static BigInteger operator |(BigInteger i1, BigInteger i2)
        //{
        //    uint[] data1 = i1.data, data2 = i2.data, data;
        //    if (data1.Length > data2.Length)
        //    {
        //        data1 = (uint[])data1.Clone();
        //    }
        //    else
        //    {
        //        data = data1;
        //        data1 = (uint[])data2.Clone();
        //        data2 = data;
        //    }
        //    for (int i = data2.Length - 1; i >= 0; i--)
        //    {
        //        data1[i] |= data2[i];
        //    }
        //    return new BigInteger(data1, false);
        //}
        //public static BigInteger operator ^(BigInteger i1, BigInteger i2)
        //{
        //    uint[] data1 = i1.data, data2 = i2.data, data;
        //    if (data1.Length > data2.Length)
        //    {
        //        data1 = (uint[])data1.Clone();
        //    }
        //    else
        //    {
        //        data = data1;
        //        data1 = (uint[])data2.Clone();
        //        data2 = data;
        //    }
        //    for (int i = data2.Length - 1; i >= 0; i--)
        //    {
        //        data1[i] ^= data2[i];
        //    }
        //    return new BigInteger(data1, false);
        //}
        //public static BigInteger operator >>(BigInteger i1, int i)
        //{
        //    return i1 << -i;
        //}
        //public static BigInteger operator <<(BigInteger i1, int i)
        //{
        //    int len = i1.length + (i + 31)/32;
        //    if (len <= 0)
        //        return Zero;
        //    int pi,pj;
        //    if(i>=0)
        //        pj = (i + 31)/32;
        //    else
        //        pj = i/32;
        //    pi = i - pj * 32;
        //    uint[] data = new uint[len], data1 = i1.data;
        //    for(int j=len-1, jj = j -pj; j>=0; j--)
        //    {
        //        if(jj<data1.Length)
        //            data[j] = data1[jj] << pi;
        //        jj--;
        //        if (jj < 0)
        //            break;
        //        data[j] |= data1[jj] >> (32 - pi);
        //    }
        //    return new BigInteger(data, i1.isNegative);
        //}
        //#endregion

        #region IEquatable<BigInteger> Members

        public override bool Equals(BigInteger other)
        {
            if (this.isNegative ^ other.isNegative)
                return false;
            uint[] d1 = this.data, d2 = other.data;
            if (this.length != other.length)
                return false;
            int i = this.length - 1;
            while (i >= 0)
            {
                if (d1[i] != d2[i])
                    return false;
                i--;
            }
            return true;
        }

        #endregion

        #region IComparable<BigInteger> Members

        public override int CompareTo(BigInteger other)
        {
            int a = this.isNegative ? -1 : 1;
            if (this.isNegative ^ other.isNegative)
                return a;
            uint[] d1 = this.data, d2 = other.data;
            int i = this.length - other.length;
            if (i != 0)
                return i*a;
            i = this.length - 1;
            while (i >= 0)
            {
                if (d1[i] != d2[i])
                    return (d1[i] > d2[i] ? 1 : -1)*a;
                i--;
            }
            return 0;
        }
        public static bool operator >=(BigInteger i1, BigInteger i2)
        {
            return i1.CompareTo(i2) >= 0;
        }
        public static bool operator >(BigInteger i1, BigInteger i2)
        {
            return i1.CompareTo(i2) > 0;
        }
        public static bool operator <=(BigInteger i1, BigInteger i2)
        {
            return i1.CompareTo(i2) <= 0;
        }
        public static bool operator <(BigInteger i1, BigInteger i2)
        {
            return i1.CompareTo(i2) < 0;
        }
        public static bool operator ==(BigInteger i1, BigInteger i2)
        {
            return i1.Equals(i2);
        }
        public static bool operator !=(BigInteger i1, BigInteger i2)
        {
            return !i1.Equals(i2);
        }

        #endregion

        #region IComparable Members

        public int CompareTo(object obj)
        {
            return ((IComparable<BigInteger>)this).CompareTo((BigInteger)obj);
        }

        #endregion

        #region IConvertible Members

        TypeCode IConvertible.GetTypeCode()
        {
            return TypeCode.Object;
        }

        bool IConvertible.ToBoolean(IFormatProvider provider)
        {
            return this.length != 0;
        }

        byte IConvertible.ToByte(IFormatProvider provider)
        {
            return (byte)this;
        }

        char IConvertible.ToChar(IFormatProvider provider)
        {
            throw new InvalidCastException();
        }

        DateTime IConvertible.ToDateTime(IFormatProvider provider)
        {
            throw new InvalidCastException();
        }

        decimal IConvertible.ToDecimal(IFormatProvider provider)
        {
            return (decimal)this;
        }

        double IConvertible.ToDouble(IFormatProvider provider)
        {
            return (double)this;
        }

        short IConvertible.ToInt16(IFormatProvider provider)
        {
            return (short)this;
        }

        int IConvertible.ToInt32(IFormatProvider provider)
        {
            return (int)this;
        }

        long IConvertible.ToInt64(IFormatProvider provider)
        {
            return (long)this;
        }

        sbyte IConvertible.ToSByte(IFormatProvider provider)
        {
            return (sbyte)this;
        }

        float IConvertible.ToSingle(IFormatProvider provider)
        {
            return (float)this;
        }

        string IConvertible.ToString(IFormatProvider provider)
        {
            return this.ToString();
        }

        object IConvertible.ToType(Type conversionType, IFormatProvider provider)
        {
            return Convert.ChangeType(this, conversionType);
        }

        ushort IConvertible.ToUInt16(IFormatProvider provider)
        {
            return (ushort)this;
        }

        uint IConvertible.ToUInt32(IFormatProvider provider)
        {
            return (uint)this;
        }

        ulong IConvertible.ToUInt64(IFormatProvider provider)
        {
            return (ulong)this;
        }

        #endregion

        #region IFormattable Members
        private static BigInteger Parse(string s, NumberStyles style, NumberFormatInfo nfi)
        {
            bool isNegative, isCurrency;
            try
            {
                if ((style & NumberStyles.AllowLeadingWhite) != 0)
                    s = s.TrimStart('\u0009', '\u000A', '\u000B', '\u000C', '\u000D', '\u0020');
                if ((style & NumberStyles.AllowTrailingWhite) != 0)
                    s = s.TrimEnd('\u0009', '\u000A', '\u000B', '\u000C', '\u000D', '\u0020');
                if ((style & NumberStyles.AllowParentheses) != 0 && s[0] == '(')
                {
                    if (s[s.Length - 1] != ')')
                        throw new Exception();
                    s = s.Substring(1, s.Length - 2);
                }
                if (isCurrency = ((style & NumberStyles.AllowCurrencySymbol) != 0 & s.StartsWith(nfi.CurrencySymbol)))
                    s = s.Substring(nfi.CurrencySymbol.Length);
                if ((style & NumberStyles.AllowLeadingSign) != 0)
                {
                    if (s.StartsWith(nfi.NegativeSign))
                    {
                        s = s.Substring(nfi.NegativeSign.Length);
                        isNegative = true;
                        goto Next;
                    }
                    else if (s.StartsWith(nfi.PositiveSign))
                    {
                        s = s.Substring(nfi.PositiveSign.Length);
                        isNegative = false;
                        goto Next;
                    }
                }
                if ((style & NumberStyles.AllowTrailingSign) != 0)
                {
                    if (s.EndsWith(nfi.NegativeSign))
                    {
                        s = s.Substring(0, s.Length - nfi.NegativeSign.Length);
                        isNegative = true;
                        goto Next;
                    }
                    else if (s.EndsWith(nfi.PositiveSign))
                    {
                        s = s.Substring(0, s.Length - nfi.PositiveSign.Length);
                        isNegative = false;
                        goto Next;
                    }
                }
                isNegative = false;
            Next:
                int[] sizes;
                string str;
                int i, j, len;
                if ((style & NumberStyles.AllowThousands) != 0)
                {
                    if (isCurrency)
                    {
                        sizes = nfi.CurrencyGroupSizes;
                        str = nfi.CurrencyGroupSeparator;
                    }
                    else
                    {
                        sizes = nfi.NumberGroupSizes;
                        str = nfi.NumberGroupSeparator;
                    }
                    if (sizes.Length > 0)
                    {
                        i = 0;
                        j = str.Length - 1 - sizes[0];
                        while (j >= 0 && sizes[i] > 0)
                        {
                            if (s.LastIndexOf(str, j, str.Length) < 0)
                                throw new FormatException();
                            j -= sizes[i] + str.Length;
                            i++;
                            if (i < sizes.Length)
                                continue;
                            i = sizes[i - 1];
                            while (j >= 0)
                            {
                                if (s.LastIndexOf(str, j, str.Length) < 0)
                                    throw new FormatException();
                                j -= i + str.Length;
                            }
                            break;
                        }
                        s = s.Replace(str, string.Empty);
                    }
                }
                if ((style & NumberStyles.AllowHexSpecifier) != 0)
                {
                    i = 0;
                    len = (s.Length + 7) / 8;
                    uint[] d = new uint[len];
                    len--;
                    if ((j = s.Length % 8) > 0)
                    {
                        d[len] = uint.Parse(s.Substring(i, j), System.Globalization.NumberStyles.HexNumber);
                        i += j;
                        j = -1;
                    }
                    j += len;
                    while (j >= 0)
                    {
                        d[j--] = uint.Parse(s.Substring(i, 8), System.Globalization.NumberStyles.HexNumber);
                        i += 8;
                    }
                    for (j = len; j >= 0 && d[j] == 0; j--) ;
                    return new BigInteger(d, j + 1, isNegative);
                }
                i = 0;
                j = s.Length % 9;
                BigInteger a;
                if (j > 0)
                {
                    a = uint.Parse(s.Substring(i, j), NumberStyles.Integer);
                    i += j;
                }
                else
                    a = Zero;
                for (j = s.Length / 9; j > 0; j--, i += 9)
                    a = a * uintD9 + uint.Parse(s.Substring(i, 9), NumberStyles.Integer);
                return new BigInteger(a.data, a.length, isNegative);
            }
            catch
            {
                throw new FormatException();
            }
        }
        public static BigInteger Parse(string s, NumberStyles style, IFormatProvider provider)
        {
            return Parse(s, style, NumberFormatInfo.GetInstance(provider));
        }
        public static BigInteger Parse(string s, IFormatProvider provider)
        {
            return Parse(s, NumberStyles.Integer, NumberFormatInfo.GetInstance(provider));
        }
        public static BigInteger Parse(string s, NumberStyles style)
        {
            return Parse(s, style, NumberFormatInfo.CurrentInfo);
        }
        public static BigInteger Parse(string s)
        {
            return Parse(s, NumberStyles.Integer, NumberFormatInfo.CurrentInfo);
        }

        public string ToString(string format, IFormatProvider formatProvider)
        {
            return this.ToString(format, NumberFormatInfo.GetInstance(formatProvider));
        }
        private string ToString(string format, NumberFormatInfo info)
        {
            if (format == null)
                return this.ToString();
            if (format.Length == 0)
                throw new ArgumentException();
            int i, j;
            switch (format[0])
            {
                case 'D':
                    if (this.length > 0)
                    {
                        BigInteger a = this, b;
                        string str;
                        StringBuilder sb = new StringBuilder();
                        while (a.length > 1)
                        {
                            b = Division(ref a, uintD9);
                            str = a.data[0].ToString("D9");
                            sb.Append(str[8]);
                            sb.Append(str[7]);
                            sb.Append(str[6]);
                            sb.Append(str[5]);
                            sb.Append(str[4]);
                            sb.Append(str[3]);
                            sb.Append(str[2]);
                            sb.Append(str[1]);
                            sb.Append(str[0]);
                            a = b;
                        }
                        str = a.data[0].ToString("D");
                        for (i = str.Length - 1; i >= 0; i--)
                            sb.Append(str[i]);
                        if (this.isNegative)
                            sb.Append(info.NegativeSign);
                        char[] s;
                        if (format.Length > 1 && (i = int.Parse(format.Substring(1))) > sb.Length)
                        {
                            s = new char[i];
                            for (j = i - sb.Length; j >= 0; j--)
                                s[j] = '0';
                            i -= sb.Length;
                        }
                        else
                        {
                            s = new char[sb.Length];
                            i = 0;
                        }
                        for (j = sb.Length - 1; j >= 0; j--, i++)
                            s[i] = sb[j];
                        return new string(s);
                    }
                    return "0";
                case 'd':
                    if (this.length > 0)
                    {
                        BigInteger a = this, b;
                        string str;
                        StringBuilder sb = new StringBuilder();
                        while (a.length > 1)
                        {
                            b = Division(ref a, uintD9);
                            str = a.data[0].ToString("d9");
                            sb.Append(str[8]);
                            sb.Append(str[7]);
                            sb.Append(str[6]);
                            sb.Append(str[5]);
                            sb.Append(str[4]);
                            sb.Append(str[3]);
                            sb.Append(str[2]);
                            sb.Append(str[1]);
                            sb.Append(str[0]);
                            a = b;
                        }
                        str = a.data[0].ToString("d");
                        for (i = str.Length - 1; i >= 0; i--)
                            sb.Append(str[i]);
                        if (this.isNegative)
                            sb.Append(info.NegativeSign);
                        char[] s;
                        if (format.Length > 1 && (i = int.Parse(format.Substring(1))) > sb.Length)
                        {
                            s = new char[i];
                            for (j = i - sb.Length; j >= 0; j--)
                                s[j] = '0';
                            i -= sb.Length;
                        }
                        else
                        {
                            s = new char[sb.Length];
                            i = 0;
                        }
                        for (j = sb.Length - 1; j >= 0; j--, i++)
                            s[i] = sb[j];
                        return new string(s);
                    }
                    return "0";
                case 'X':
                    if (this.length > 0)
                    {
                        StringBuilder sb = new StringBuilder(this.length * 8);
                        i = this.length - 1;
                        sb.AppendFormat("{0:X}", this.data[i--]);
                        while (i >= 0)
                            sb.AppendFormat("{0:X8}", this.data[i--]);
                        if (format.Length > 1 && (i = int.Parse(format.Substring(1))) > sb.Length)
                            return (this.isNegative ? info.NegativeSign : string.Empty) + new string('0', i - sb.Length) + sb.ToString();
                        return (this.isNegative ? info.NegativeSign : string.Empty) + sb.ToString();
                    }
                    return "0";
                case 'x':
                    if (this.length > 0)
                    {
                        StringBuilder sb = new StringBuilder(this.length * 8);
                        i = this.length - 1;
                        sb.AppendFormat("{0:x}", this.data[i--]);
                        while (i >= 0)
                            sb.AppendFormat("{0:x8}", this.data[i--]);
                        if (format.Length > 1 && (i = int.Parse(format.Substring(1))) > sb.Length)
                            return (this.isNegative ? info.NegativeSign : string.Empty) + new string('0', i - sb.Length) + sb.ToString();
                        return (this.isNegative ? info.NegativeSign : string.Empty) + sb.ToString();
                    }
                    return "0";
            }
            throw new ArgumentException();
        }
        public string ToString(string format)
        {
            return this.ToString(format, NumberFormatInfo.CurrentInfo);
        }
        public override string ToString()
        {
            return this.ToString("D", NumberFormatInfo.CurrentInfo);
        }
        #endregion

        public BigInteger Clone()
        {
            return new BigInteger(this.data, this.length, this.isNegative);
        }

        public override SignTypes Sign
        {
            get
            {
                if (isNegative)
                    return SignTypes.Negative;
                return length == 0 ? SignTypes.Zero : SignTypes.Positive;
            }
        }

        public override bool Equals(object obj)
        {
            if (obj is BigInteger)
                return this.Equals((BigInteger)obj);
            return false;
        }

        public override int GetHashCode()
        {
            uint u = this.isNegative ? uint.MaxValue : 0;
            for (int i = length - 1; i >= 0; i--)
            {
                u ^= data[i];
            }
            return length ^ (int)u;
        }

        public override BigInteger DivRem(BigInteger divisor, out BigInteger remainder)
        {
            remainder = this;
            return Division(ref remainder, divisor);
        }
    }
}
